import { h } from "vue"

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}


function inorderTraversal(root: TreeNode | null): number[] {
  const list: number[] = []
  function fn(head: TreeNode | null) {
    if (!head) {
      return
    } else {
      fn(head.left)
      list.push(head.val)
      fn(head.right)
    }
  }
  fn(root)
  return list
};


/**
 * 迭代写法 手动维护调用栈
 */
function inorderTraversal2(root: TreeNode | null): number[] {
  const list = []
  const stack = []
  while (root || stack.length) {
    while (root) {
      stack.push(root)
      root = root.left
    } // 直至左为 null
    root = stack.pop() as TreeNode
    list.push(root.val)
    root = root.right
  }
  return list
};